package string;

import java.util.HashMap;
import java.util.Map;

/**
 28.实现 strStr() 函数。

 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

 示例 1:

 输入: haystack = "hello", needle = "ll"
 输出: 2
 示例 2:

 输入: haystack = "aaaaa", needle = "bba"
 输出: -1

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/implement-strstr
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 KMP
 */
public class Q28_StrSt {
    //1.截取比较
    private void strStrSub (String haystack, String needle) {
        if (haystack==null || needle == null) {
            System.out.println(-1);
            return;
        }
        int neeLen = needle.length();
        int hayLen = haystack.length();
        for (int idx=0; idx<=hayLen-neeLen; idx++) {
            String destStr = haystack.substring(idx, idx+neeLen);
            if (destStr.equals(needle)) {
                System.out.println(idx);
                return;
            }
        }
        System.out.println(-1);
        return;
    }

    //2.暴力 时间复杂度 O(M*N)
    private void strStForce (String haystack, String needle) {
        if (haystack==null || needle == null) {
            System.out.println(-1);
            return;
        }
        int hIdx = 0, nIdx = 0;
        int hLen = haystack.length();
        int nLen = needle.length();
        while (hIdx < hLen && nIdx < nLen) {
            if (haystack.charAt(hIdx) == needle.charAt(nIdx)) {
                hIdx++;
                nIdx++;
            } else {
                hIdx = hIdx - nIdx + 1;
                nIdx = 0;
            }
        }
        if (nIdx == nLen) {
            System.out.println(hIdx - nIdx);
            return;
        }
        System.out.println(-1);
        return;
    }

    //3.Sunday算法
    private void strStSunday(String haystack, String needle) {
        if (haystack==null || needle == null) {
            System.out.println(-1);
            return;
        }
        int hLen = haystack.length();
        int nLen = needle.length();
        int hIdx = 0, nIdx = 0;
        int endHIdx = nLen;
        int endNIdx;
        while (hIdx < hLen - nLen) {
            if (haystack.charAt(hIdx) == needle.charAt(nIdx)) {
                if (nIdx == nLen-1) {
                    System.out.println(hIdx - nIdx);
                    return;
                }
                nIdx++;
                hIdx++;
            } else {//找到下一次开始匹配的位置
                //遍历查找此时子串与源串[hIdx+nLen]相等的最右位置
                for(endNIdx=nLen-1; endNIdx>=0; endNIdx--) {
                    if(needle.charAt(endNIdx) == haystack.charAt(endHIdx))
                        break;
                }
                //hIdx为下一次匹配源串开始首位 Sunday算法核心：最大限度跳过相同元素
                hIdx = endHIdx - endNIdx;
                //nIdx依然为子串首位
                nIdx = 0;
                //endHIdx为下一次参与匹配的源串最后一位元素的下一位
                endHIdx = hIdx + nLen;
                //当下一次参与匹配的源串字数的最后一位的下一位超过源串长度时
                if(endHIdx > hLen) {
                    System.out.println(-1);
                    return;
                }
            }
        }
    }

    private int maxNum = 1005;
    private int[] shift = new int[maxNum];
    private int Sunday(String hay, String nee) {
        int hLen = hay.length();
        int nLen = nee.length();

        // 默认值，移动m+1位
        for(int i = 0; i < maxNum; i++) {
            shift[i] = nLen + 1;
        }

        // 模式串P中每个字母出现的最后的下标
        // 所对应的主串参与匹配的最末位字符的下一位字符移动到该位，所需要的移动位数
        for(int i = 0; i < nLen; i++) {
            shift[nee.charAt(i)] = nLen - i;
        }

        // 模式串开始位置在主串的哪里
        int hIdx = 0;
        // 模式串已经匹配到的位置
        int nIdx;
        while(hIdx <= hLen - nLen) {
            nIdx = 0;
            while(hay.charAt(hIdx + nIdx) == nee.charAt(nIdx)) {
                nIdx++;
                // 匹配成功
                if(nIdx >= nLen) {
                    System.out.println(hIdx);
                    return hIdx;
                }
            }
            // 找到主串中当前跟模式串匹配的最末字符的下一个字符
            // 在模式串中出现最后的位置
            // 所需要从(模式串末尾+1)移动到该位置的步数
            //
            // 模式串在源串中的下一个位置，
            // 如初始情况源串bbcaabcbc，模式串abc，即源[3] bbca->a
            // 不匹配情况下，判断源串 a 是否在模式串abc中；得到偏移量0+3，源串开始位置3，移动源串位置，得
            // bbcaabcbc
            //    abc
            // 这时 即源[6] bbcaabc->c
            // 判断源串 c 是否在模式串abc中；得到偏移量3+1，即源串开始位置，移动源串位置，得
            // bbcaabcbc
            //     abc
            // 使得模式串的最右边出现的字符和（若有）源串下一个字符匹配
            hIdx += shift[hay.charAt(hIdx + nLen)];
        }
        System.out.println(-1);
        return -1;
    }


    public static void main(String[] args) {
        new Q28_StrSt().strStrSub("", "");
        new Q28_StrSt().strStForce("abc", "bc");
        new Q28_StrSt().strStSunday("bbcaabcb", "abc");
        int s = new Q28_StrSt().Sunday("bbcaabcbc", "abc");
        System.out.println(s);
    }

}
